package leetcode;

/*
292. Nim 游戏
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
*/

import java.util.ArrayDeque;
import java.util.Queue;

public class problems_292 {
    public static void main(String[] args) {
        System.out.println(new Solution().canWinNim(8));
    }

    static class Solution {
        public boolean canWinNim(int n) {
            return !(n % 4 == 0);
        }

//        // 动态规划的方式
//        public boolean canWinNim(int n) {
//            if(n <= 3) return true;
//            // 初始化
//            Queue<Boolean> dp = new ArrayDeque();
//            dp.offer(true);
//            dp.offer(true);
//            dp.offer(true);
//            Boolean last = true;
//            for (int i = 4; i < n + 1; i++) {
//                // 取得的下三个节点，都是对方赢时，返回失败
//                last = dp.stream().filter(bol->!bol).count() > 0;
//                dp.offer(last);
//                dp.poll();
//            }
//            return last;
//        }



//        // 动态规划的方式
//        public boolean canWinNim(int n) {
//            // 初始化
//            Boolean[] dp = new Boolean[n + 1];
//            if (n >= 1) dp[1] = true;
//            if (n >= 2) dp[2] = true;
//            if (n >= 3) dp[3] = true;
//            for (int i = 4; i < n + 1; i++) {
//                // 取得的下三个节点，都是对方赢时，返回失败
//                dp[i] = !(dp[i-1] && dp[i-2] && dp[i-3]);
//            }
//            return dp[n];
//        }
    }
}